#include "heap.h"

void HeapPrint(Heap* hp)
{
	assert(hp);
	int i = 0;
	for (i = 0; i < hp->size; i++)
	{
		printf("%d ", hp->a[i]);
	}
	printf("\n");
}

void swap(HPDataType* a, HPDataType* b)
{
	int tmp = 0;
	tmp = *a;
	*a = *b;
	*b = tmp;
}

void HeapInit(Heap* hp)
{
	hp->a = (HPDataType*)malloc(sizeof(HPDataType));
	if(hp->a == NULL)
	{
		exit(-1);
	}
	hp->capacity = 0;
	hp->size = 0;
}

void HeapAdjustDown(Heap* hp)
{
	assert(hp);
	int i = 0;
	int left = 2 * i + 1;
	int big = 0;
	while (left < hp->size)
	{
		big = left;
		if ((hp->a[left] < hp->a[left+1]) && (left + 1 < hp->size))
		{
			big= left + 1;
		}
		if (hp->a[i] < hp->a[big])
		{
			swap(&hp->a[i], &hp->a[big]);
		}
		i = big;
		left = 2 * i + 1;
	}
}

void HeapAdjustUp(Heap* hp)
{
	assert(hp);
	int i = 0;
	int n = 0;
	n = hp->size-1;
	int big = 0;
	while (i >= 0)
	{
		big = n;
		if (((n - 1) / 2 == (n - 1 - 1) / 2)&&((n-2)>=0))
		{
			if ((hp->a[n] < hp->a[n - 1]))
			{
				big = n - 1;
			}
		}
		i = (big - 1) / 2;
		if ((big - 1) < 0)
		{
			break;
		}
		if ((hp->a[i] < hp->a[big]))
		{
			swap(&hp->a[i], &hp->a[big]);
		}
		n = i;
	}
}

void HeapAdjustUp1(Heap* hp,int j)
{
	assert(hp);
	int i = 0;
	int n = 0;
	n = j;
	int big = 0;
	while (i >= 0)
	{
		big = n;
		if (((n - 1) / 2 == (n - 1 - 1) / 2) && ((n - 2) >= 0))
		{
			if ((hp->a[n] < hp->a[n - 1]))
			{
				big = n - 1;
			}
		}
		i = (big - 1) / 2;
		if ((big - 1) < 0)
		{
			break;
		}
		if ((hp->a[i] < hp->a[big]))
		{
			swap(&hp->a[i], &hp->a[big]);
		}
		n = i;
	}
}

void HeapCreate(Heap* hp, HPDataType* a, int mm)
{
	hp->a = (HPDataType*)malloc(sizeof(Heap) * (mm * 2));
	if (hp->a == NULL)
	{
		exit(-1);
	}
	hp->capacity = 2 * mm;
	int j = 0;
	hp->a = a;
	hp->size = mm - 1;
	for (j = 2; j < hp->size; j++)
	{
		HeapAdjustUp1(hp,j);
	}
}

void HeapAdjustDown1(Heap* hp, int j)
{
	assert(hp);
	int i = j;
	int left = 2 * i + 1;
	int big = 0;
	while (left < hp->size)
	{
		big = left;
		if ((hp->a[left] < hp->a[left + 1]) && (left + 1 < hp->size))
		{
			big = left + 1;
		}
		if (hp->a[i] < hp->a[big])
		{
			swap(&hp->a[i], &hp->a[big]);
		}
		i = big;
		left = 2 * i + 1;
	}
}
//
//void HeapCreate(Heap* hp, HPDataType* a, int mm)
//{
//	hp->a = (HPDataType*)malloc(sizeof(Heap) * (mm * 2));
//	if (hp->a == NULL)
//	{
//		exit(-1);
//	}
//	hp->capacity = 2 * mm;
//	int j = 0;
//	hp->a = a;
//	hp->size = mm - 1;
//
//	for (j = (hp->size-1)/2; j>=0; j--)
//	{
//		HeapAdjustDown1(hp,j);
//	}
//}


void HeapCheck(Heap* hp)
{
	assert(hp);
	if (hp->capacity == 0)
	{
		hp->a = (HPDataType*)malloc(sizeof(HPDataType) * MM);
		if (hp->a == NULL)
		{
			exit(-1);
		}
		hp->capacity = MM;
	}
	if ((hp->size >= hp->capacity) && (hp->capacity != 0))
	{
		HPDataType* P = (HPDataType*)realloc(hp->a, sizeof(HPDataType) * 2 * hp->capacity);
		if (P == NULL)
		{
			exit(-1);
		}
		hp->capacity = 2 * hp->capacity;
		hp->a = P;
	}
}

void HeapPush(Heap* hp, HPDataType x)
{
	HeapCheck(hp);
	hp->a[hp->size] = x;
	hp->size++;
	if (hp->size > 1)
	{
		int j = 0;
		for (j = (hp->size-1)/2; j>=0; j--)
		{
			HeapAdjustDown1(hp,j);
		}
	}
}

void HeapPop(Heap* hp)
{
	assert(hp);
	if (hp->size == 0)
	{
		return;
	}
	hp->size--;
	swap(&hp->a[0], &hp->a[hp->size]);
	
	HeapAdjustDown(hp);
}

HPDataType HeapTop(Heap* hp)
{
	assert(hp);
	if (hp->size == 0)
	{
		exit(-1);
	}

	return hp->a[0];
}

int HeapSize(Heap* hp)
{
	assert(hp);
	return hp->size;
}

bool HeapEmpty(Heap* hp)
{
	assert(hp);
	if (hp->size == 0)
	{
		return true;
	}
	else
	{
		return false;
	}
}

void HeapDestory(Heap* hp)
{
	free(hp->a);
	hp->a = NULL;
	hp->capacity = 0;
	hp->size = 0;
	free(hp);
	hp = NULL;
}

void HeapSort(Heap* hp, HPDataType* b, int siz)
{
	assert(hp);
	int i = 0;
	for (i = 0; i < siz; i++)
	{
		HeapPush(hp, b[i]);
	}
	//HeapPrint(hp);
	Heap* HP = hp;
	for (i = 0; i < siz - 1; i++)
	{
		HP->size--;
		swap(&HP->a[0], &HP->a[HP->size]);
		//HeapPrint(HP);
		b[siz - i - 1] = HP->a[HP->size];
		HeapAdjustDown(HP);
	}
	b[0] = HP->a[HP->size - 1];

}

void HeapSort1(Heap* hp, HPDataType* b, int siz)
{
	assert(hp);
	int i = 0;
	for (i = 0; i < siz; i++)
	{
		HeapPush(hp, b[i]);
	}
	int si = hp->size;
	for (i = 0; i < siz - 1; i++)
	{
		hp->size--;
		swap(&hp->a[0], &hp->a[hp->size]);
		//HeapPrint(hp);
		HeapAdjustDown(hp);
	}
	hp->size = si;
	HeapPrint(hp);

}

void HeapSort2(Heap* hp)
{
	assert(hp);
	int i = 0;
	int si = hp->size;
	while(hp->size)
	{
		hp->size--;
		swap(&hp->a[0], &hp->a[hp->size]);
		HeapAdjustDown(hp);
	}
	hp->size = si;
}

void HeapAdjustDownso(Heap* hp,int j)
{
	assert(hp);
	int i = 0;
	int left = 2 * i + 1;
	int big = 0;
	while (left < j)
	{
		big = left;
		if ((hp->a[left] < hp->a[left + 1]) && (left + 1 < hp->size))
		{
			big = left + 1;
		}
		if (hp->a[i] < hp->a[big])
		{
			swap(&hp->a[i], &hp->a[big]);
		}
		i = big;
		left = 2 * i + 1;
	}
}